package org.example.leetCode;

/**
 * 35. 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 */
public class Code35 {
    public static int searchInsert(int[] nums, int target) {
        int result = nums.length / 2;

        int left = 0;
        int right = nums.length-1;
        int flag;
        int index = 0;
        while (left <= right&&right<nums.length) {
            index = left+(right - left) / 2;
            flag = nums[index];
            if (flag == target) {
                return index;
            } else if (flag < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
        return left;
    }
    public static void main(String[] args) {
        int[] nums = {1, 3};
        int target1 = 1;
        int target2 = 2;
        int target3 = 7;
        int target4 = 0;

        System.out.println("Index for " + target1 + ": " + searchInsert(nums, target1)); // Expected output: 2
        System.out.println("Index for " + target2 + ": " + searchInsert(nums, target2)); // Expected output: 1
        System.out.println("Index for " + target3 + ": " + searchInsert(nums, target3)); // Expected output: 4
        System.out.println("Index for " + target4 + ": " + searchInsert(nums, target4)); // Expected output: 0
    }
}
